package com.dataStructures.sort;

import java.util.Arrays;

/**
 * 冒泡排序（时间复杂度 O(n^2)）
 */
public class BubbleSort {
	public static void main(String[] args) {
		int[] arr = {5,2,3,1,4};
		System.out.println("排序前：" + Arrays.toString(arr));
		bubbleSort(arr);
		System.out.println("排序后：" + Arrays.toString(arr));

		// 批量测试
//		int[] arrBatch = new int[10000000];
//		for (int i = 0; i < 10000000; i++) {
//			arrBatch[i] = (int) (Math.random() * 10000000);
//		}
//		long begin = System.currentTimeMillis();
//		bubbleSort(arrBatch);
//		System.out.println("coast time:" + (System.currentTimeMillis() - begin));
	}

	public static void bubbleSort(int[] arr) {
		int temp;
		// 是否进行过交换（优化点：在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。）
		boolean flag = false;
		// 进行多少趟比较
		for (int i = 0; i < arr.length - 1; i++) {
			// 每一趟进行的比较次数
			for (int j = 0; j < arr.length - 1 - i; j++) {
				// 进行比较，如果前边的数 > 后边，则交换
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
					flag = true;
				}
			}
			if (!flag) {
				break;
			}
			flag = false;
		}
	}
}
